/*
 * 跳格子
 * 
 * 题目描述
小明和朋友们一起玩跳格子游戏，

每个格子上有特定的分数 score = [1, -1, -6, 7, -17, 7]，

从起点score[0]开始，每次最大的步长为k，请你返回小明跳到终点 score[n-1] 时，能得到的最大得分。

输入描述
第一行输入总的格子数量 n

第二行输入每个格子的分数 score[i]

第三行输入最大跳的步长 k

输出描述
输出最大得分

备注
格子的总长度 n 和步长 k 的区间在 [1, 100000]
每个格子的分数 score[i] 在 [-10000, 10000] 区间中
用例
输入	6
1 -1 -6 7 -17 7
2
输出	14
说明	无

 */

 /**
  * 
  题目解析
假设第 i 个格子的最大得分为 dp[i]，那么存在如下递推公式：

dp[i] = max(dp[i-k], dp[i-k+1], ...., dp[i-2], dp[i-1]) + score[i]
可以发现，dp[i]的状态取决于 dp数组的 i-k ~ i-1 范围内的最大值状态。即第 i 个格子想要最大得分，可以从第 i-k 到 第 i-1 个格子中选择一个最大得分的格子起跳。

因此本题难点就变成了：求一个数组的任意长度为k的子区间内的最大值。

高效的求解办法是利用单调队列，具体可以看：

LeetCode - 239 滑动窗口最大值-CSDN博客
  */

import java.util.LinkedList;
import java.util.Scanner;

public class 跳格子 {
   public static void main(String[] args) {

    try{

        Scanner scanner = new Scanner(System.in);

        //格子数量
        int gzCount = scanner.nextInt();
        //格子分数数组
        int[] gzScoreArr = new int[gzCount];

        for(int n=0; n<gzCount; n++){
            gzScoreArr[n] = scanner.nextInt();
        }

        //最大步长
        int maxStep = scanner.nextInt();

        //第i个格子，可以从第i-k个格子~第i-1个格子调过来，因此本题滑窗的长度相当于k+1
        int screenLen = maxStep+1;
        //dp[i]表示跳到第i个格子能得到的最大分数
        int[] resultScore = new int[gzCount];
        resultScore[0] = gzScoreArr[0];

        //单调队列（单调递减，队首是滑窗最大值）
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(resultScore[0]);

        //初始滑窗的形成过程（即只有新增尾部元素的过程）
        for (int i = 1; i < Math.min(screenLen, gzCount); i++) {

            // 注意当len > n时, 需要取n, 此时只有滑窗形成过程，没有滑窗移动过程

            // dp[i] = max(dp[0]~dp[i-1]) + scores[i]
            // 即单调队列队首保存的是max(dp[0]~dp[i-1])
            resultScore[i] = queue.getFirst() + gzScoreArr[i];
        
            // 保持单调队列的单调递减性，即如果后入队的dp[i] 大于 队尾元素，则队尾元素出队
            while (queue.size() > 0 && resultScore[i] > queue.getLast()) {
                queue.removeLast();
            }
        
            // 当队尾没有比dp[i]更小的元素后，dp[i]才能入队
            queue.addLast(resultScore[i]);

        }

        // 滑窗的右移过程（即相较于老滑窗失去一个首元素，新增一个尾元素）
        for (int i = screenLen; i < gzCount; i++) {
                // 如果滑窗失去的元素dp[i - len]，和单调队列的队首元素queue[0]相同，则单调队列需要弹出头部元素
                if (resultScore[i - screenLen] == queue.getFirst()) {
                    queue.removeFirst();
            }
    
            // 下面逻辑同之前
            resultScore[i] = queue.getFirst() + gzScoreArr[i];
    
            while (queue.size() > 0 && resultScore[i] > queue.getLast()) {
                queue.removeLast();
            }
    
            queue.addLast(resultScore[i]);
        }

        System.out.println(resultScore[gzCount - 1]);


    }catch(Exception e){
        e.printStackTrace();
    }
   } 
}
